package com.wzq.solution;

class Solution34 {
    public static int[] searchRange(int[] nums, int target) {
        
        int l=0;
        int r=nums.length-1;
        int[] rst = new int[]{-1,-1};
        int i=0;
        while(l<=r){

            i = (l+r)/2;
            if(nums[i] > target){
                r=i-1;
            }else if(nums[i] < target){
                l=i+1;
            }else{
                rst[0]=i;
                rst[1]=i;
                int lr =i-1;
                int rl =i+1;
                while (l<=lr){
                    i = (l+lr)/2;
                    if(nums[i] == target){
                        rst[0]=i;
                        lr=i-1;
                    }else{
                        l=i+1;
                    }
                }

                while (rl<=r){
                    i = (rl+r)/2;
                    if(nums[i] == target){
                        rst[1]=i;
                        rl=i+1;

                    }else{
                        r=i-1;

                    }
                }
                break;


            }
        }

        return rst;
    }

    public static int[] searchRange2(int[] nums, int target) {

        int l=0;
        int r=nums.length-1;
        int[] rst = new int[]{-1,-1};
        int i=0;
        while(l<=r){

            i = (l+r)/2;
            if(nums[i] > target){
                r=i-1;
            }else if(nums[i] < target){
                l=i+1;
            }else{
                rst[0]=i;
                rst[1]=i;
                int lr =i-1;
                int rl =i+1;
                while (l<=lr){
                    i = (l+lr)/2;
                    if(nums[i] == target){
                        rst[0]=i;
                        lr=i-1;
                    }else{
                        l=i+1;
                    }
                }

                while (rl<=r){
                    i = (rl+r)/2;
                    if(nums[i] == target){
                        rst[1]=i;
                        rl=i+1;

                    }else{
                        r=i-1;

                    }
                }
                break;


            }
        }

        return rst;
    }



    public static void main(String[] args) {
        searchRange(new int[]{10,10},10);
    }
}